1. Field of the Invention
The present invention relates to a Booth Array type multiplying circuit which rapidly processes mutual binary multiplication in a data processing system in an electronic computer and the like, and to be more particular, firstly to a multiplying circuit including a function of sign extension of a multiplier, and secondly to a multiplying circuit which executes a desired multiplication by dividing it into a plurality of operation cycles, obtaining an intermediate result which is a partial sum of partial products in respective operation cycles, and repeating the operation cycles by transferring the intermediate result to the following operation cycle to obtain a multiplication result which is a sum of the entire partial products.
2. Description of the Related Art
It is generally known that, by Booth algorithm, the multiplication result by two's complement representation is obtained without arithmetic pre-processing or post-processing with respect to integers by two's complement representation, and is utilized in a multiplying circuit, in a data processing system.
At first, a multiplying algorithm and a sign extension of multiplier by the Booth algorithm are described, and then a conventional realizing method by its hardware is described.
The Booth algorithm is an algorithm devised by Andrew Donald Booth as a method of executing the multiplication rapidly. In general, at the time of executing the multiplication of digital data, multiplier data is divided into a plurality of bits to multiply with a multiplicand to produce partial products (multiples), which are added to obtain the multiplication result. In short, the Booth algorithm is that, at the time of executing the multiplication, by overlapping highest bits of the lower side division on respective divisions of the multiplier and adopting signed digit numbers, it is convenient when using digital numbers whose resulting multiplies are .+-.2, .+-.4 and so on, and is advantageous in that the number by two's complement representation can be multiplied directly.
FIG. 1 and FIG. 2 are schematic views showing a method of multiplication by the Booth algorithm conventionally used in general. Hereupon, an example of using the second degree Booth algorithm is shown.
Multiplication of a multiplicand X and a multiplier Y is executed by, as shown in FIG. 1 wherein the multiplicand X is shown as first input data and the multiplier Y is shown as second input data, at first, multiplying all bits of the multiplicand X by partial bits of the multiplier Y to calculate the partial products successively, and then obtaining a summation of the partial products.
In the second degree Booth algorithm, one partial product is produced for every two bits of the multiplier Y. Thus, as shown in FIG. 1, in the 32 bits.times.32 bits multiplication, the first. 2 bits Y&lt;1:0&gt; corresponding portion of the multiplier Y and the multiplicand X are multiplied to produce the first partial product, then the next 2 bits Y&lt;3:2&gt; corresponding portion of the multiplier Y and the multiplicand X are multiplied to produce the second partial product, and the partial products are produced thereafter successively to finally produce the 16th partial product by multiplying the last 2 bits Y&lt;31:30&gt; corresponding portion of the multiplier Y and the multiplicand X.
In this way, in the 32 bits.times.32 bits multiplication, 16 partial products are produced from the 1st to 16th partial products, and finally the 64-bit multiplication result P is obtained as their summation.
Operation rules of the partial product are shown in a table in FIG. 2.
The table in FIG. 2 shows the relationship between inputs, outputs and corresponding multiples of the Booth algorithm, more specifically, it shows 3-bit input signal values to Booth decoders to be described later, corresponding 3-bit output signal values and corresponding multiple generating circuit outputs.
The multiplier Y (input to the Booth decoders) used in the partial product operations is 3 bits, and the partial product is obtained in a 2-bit unit. And hence, bits of the multiplier Y having indices of odd number are inputted to two Booth decoders. That is, though the partial products of Y&lt;2i+1&gt; and Y&lt;2i&gt; are obtained at tile time of obtaining the "i+1"th partial product, the lower side Y&lt;2i-1&gt; is also used. Specifically, for example, at the time of obtaining the second partial product, the lower side Y&lt;1&gt; is also used besides Y&lt;3&gt; and Y&lt;2&gt;.
However, though Y&lt;1&gt; and Y&lt;0&gt; are used at the time of obtaining the first partial product, "0" is used as the lower side bit.
Hereinafter, Y&lt;2i-1&gt; used at the time of calculating the "i+1"th partial product is referred to as a carry multiplier.
Thus, for example, Y&lt;3&gt; is used as the lower side bit at the time of obtaining a third partial product besides being used at the time of obtaining the second partial product, as described above.
Next, a sign extension is described.
For example, in a data processor executing multiplication on the multiplier having three kinds of effective widths of 32 bits, 16 bits and 8 bits, in many cases, a multiplier having a maximum 32-bit width is used also in the operation of other sizes. In this case, for example, when executing the multiplication on the 8-bit multiplier, for obtaining a correct multiplication result, the higher 24 bits of a 32-bit multiplier input must be set to a specific value. At this time, a method of deciding the value of the higher 24 bits among the 32 bits when multiplier data is the signed binary numbers is called the sign extension method.
Since signed data is the object in the Booth algorithm, when the multiplier data is the unsigned binary numbers, the sign extension is effected after converting it (all invalid portions on the higher side of the effective width are made "0") into the signed data.
In the sign extension, the sign bits which are the highest bits of the effective data must be reproduced into all bits of higher invalid data.
FIG. 3 is a schematic view showing, as an example, a method of sign extension of 16-bit signed data to 32-bit signed data, and FIG. 4 is a schematic view showing a method of sign extension of 8-bit signed data to the 32-bit signed data.
In FIG. 3 and FIG. 4, the signed bit designated by reference character S is reproduced into all of the higher bits.
Specifically, as shown in FIG. 3, in case of extending the 16-bit signed data (effective data is 15 bits) to the 32-bit signed data, a value of the highest signed bit S of 16-bit signed data is reproduced into all 17 bits, including itself, at the higher side of the 32-bit data, and the lower 15 bits are the effective data.
Similarly, as shown in FIG. 4, in case of extending the 8-bit signed data (effective data is 7 bits) to the 32-bit signed data, a value of the highest signed bit S of the 8-bit signed data is reproduced into all 25 bits, including itself, at the higher side of the 32-bit data, and the lower 7 bits are the effective data.
Next, as an example of configuration of the hardware of the conventional multiplying circuit, by Booth algorithm, the case of including a sign extension function of the multiplier is described.
FIG. 5 is a block diagram showing an example of configuration of such conventional multiplying circuit.
FIG. 6 is a truth table for explaining the operation of a sign extension control circuit 50 constituting the multiplying circuit shown in FIG. 5.
In the conventional circuit configuration shown in FIG. 5, the 32 bits.times.32 bits multiplication is effected at a time. As multiplier sizes, three kinds of 32 bits (word), 16 bits (half word) and 8 bits (byte) are used.
In FIG. 5, numeral 1 designates a multiplier input Y&lt;31:0&gt; of 32-bit, numeral 2 designates a multiplicand input X&lt;31:0&gt; of 32-bit, numeral 3 designates a half word size signal, numeral 4 designates a byte size signal, numeral 50 designates a sign extension control circuit, numeral 60 designates a sign extension control signal and numerals 70a and 70b designate a sign extension lower circuit and a sign extension higher circuit.
The half-word size signal 8 showing that an effective portion of the multiplier Y is the hall: word (Y&lt;15:0&gt;), and the byte size signal 4 showing that the effective portion of the multiplier Y is a byte (Y&lt;7:0&gt;) are both inputted to the sign extension control circuit 80, and Y&lt;7&gt; corresponding to the byte size sign bit in the multiplier input 1, and Y&lt;15&gt; corresponding to the half word size sign bit are also inputted to the sign extension control circuit 50.
The sign extension control signal 60 which is an output signal of the sign extension control circuit 50 is to be described later.
Numeral 8 designates sign extension multiplier signals (multiplier signals after sign extension) which are output signals from the sign extension lower circuit 70a and the sign extension higher circuit 70b, numerals 9a to 9p designate Booth decoders (BD) and numeral 1.0 designates a multiplication array circuit.
The Booth decoders 9a to 9p are so constituted that, the 3-bit input signal value as shown in FIG. 2, the corresponding 3-bit output signal value and the corresponding multiple generating circuit output are obtained.
The multiplication array circuit 10 includes multiple generating circuits 11a to 11p and partial product adding circuits (ADD) 12a to 12p.
Numeral 30 designates an output of multiplication result &lt;63:1&gt;.
The operation of such a conventional multiplying circuit is as follows.
As described above, the byte size signal 4 showing that the effective portion of the multiplier Y is &lt;7:0&gt;, the half word size signal 3 showing that the effective portion of the multiplier Y is the half word of Y&lt;15:0&gt;, the sign bit Y(7) which is the byte size in the multiplier Y of the multiplier input 1 and the sign bit Y&lt;15&gt; which is the half word are inputted to the sign extension control circuit 50, which outputs either "0" or bits Y&lt;7&gt; and Y&lt;15&gt; in response to the half word size signal 3 or byte size signal 4 as the sign extension control signal 60.
FIG. 6 shows the relationship between the input and output signals of the sign extension control circuit 50, in other words, the operation of the sign extension control circuit 50 is shown in the form of a truth table.
The sign extension control signal 60, which is the output signal of the sign extension control circuit 50, includes a higher half word set signal (SETHW), a higher half word reset signal (RSTHW), a second lower byte set signal (SETBT) and a second lower byte reset signal (RSTBT).
For example, at the time of multiplying byte size data, when the byte size signal 4 is "1" (the half-word size signal 3 is "0"), and Y&lt;7&gt; which is the sign bit S is "1", both the higher half word set signal (SETHW) and the second lower byte set signal (SETBT) become "1".
Also, at the time of multiplying half word size data, when the half word size signal 3 is "1" (the byte size signal 4 is "0") and Y&lt;15&gt; which is the sign bit S is "0", the higher half word reset signal (RSTHW) becomes "1".
The higher half word set signal (SETHW) and the higher half word reset signal (RSTHW) are inputted to the sign extension higher circuit 70b, and the second lower byte set signal (SETBT) and the second lower byte reset signal (RSTBT) are inputted to the sign extension lower circuit 70a.
While, the multiplier Y is inputted from the multiplier input 1, the higher half word Y&lt;31:16&gt; is inputted to the sign extension higher circuit 70b, and the second lower byte Y&lt;15:8&gt; is inputted to the sign extension lower circuit 70a. The other bits Y&lt;7:0&gt; are inputted to the Booth decoders 9a to 9d by each 2 bits.
In the sign extension higher circuit 70b, when the corresponding higher word set signal (SETHW) is "1", its output or all bits of SY&lt;31:16&gt; which is the sign extension multiplier signal 8 are forcibly made "1", and when the higher half word reset signal (RSTHW) is "1", its output or all bits of SY&lt;31:16&gt; which is the sign extension multiplier signal 8 are forcibly made "0".
When both the higher half word set signal (SETHW) and the higher half word reset signal (RSTHW) are "0", the input value of Y&lt;31:16&gt; is inputted intact to SY&lt;31:16&gt; which is the sign extension multiplier signal 8.
The signal extension lower circuit 70a also operates in the same way as the sign extension higher circuit 70b.
That is, in the sign extension lower circuit 70a, when the corresponding second lower byte set signal (SETBT) is "1" its output or all bits of SY&lt;15:8&gt; which is the sign extension multiplier signal 8 is forcibly made "1" and when the second lower byte reset signal (RSTBT) is "1", its output or all bits of SY&lt;15:8&gt; which is the sign extension multiplier signal 8 is forcibly made "0".
When both the second lower byte set signal (SETBT) and the second lower byte reset signal (RSTBT) are "0", the Y&lt;15:8&gt; input value is outputted intact to SY&lt;15:8&gt; which is the sign extension multiplier signal 8.
An example of specific circuit configuration by logic gates of the sign extension higher circuit 70b is shown in a circuit, diagram of FIG. 7.
The circuit shown in FIG. 7 is the circuit realizing functions of the sign extension higher circuit 70b as described above, and is constituted by one OR function and one AND function per one bit.
Specifically, each signal of the bits Y&lt;16&gt; to Y&lt;31&gt; is inputted to each one input, terminal of 2-input NOR gates 71, and the higher half word set signal (SETHW) is inputted to the other input terminal thereof. Each output signal of the NOR gates 71 is inputted to one input terminal of each 2-input AND gate 72, and the higher half word reset signal (RSTHW) is inputted to the other input terminal thereof. Each output signal of the AND gate 72 is the signal of the bits SY&lt;16&gt; to SY&lt;31&gt; of the sign extension multiplier signal 8.
The sign extension lower circuit 70a is also constituted similarly, and the input signals are the second lower byte set signal (SETBT) and second lower byte reset signal (RSTBT) in place of the higher half word set signal (SETHW) and higher half word reset signal (RSTHW), and signals of the bits Y&lt;15&gt; to Y&lt;8&gt; in place of the signals of the bits Y&lt;31&gt; to Y&lt;16&gt;.
The signals SY&lt;31:16&gt; in the sign extension multiplier signal 8 outputted from the sign extension lower circuit 70b are inputted to the Booth decoders 9i to 9p, the signals SY&lt;15:8&gt; in the sign extension multiplier signal 8 outputted from the sign extension lower circuit 70a are inputted to the Booth decoders 9e to 9h, and further, the signals Y&lt;7:0&gt; which are a portion of the multiplier input 1 are inputted to the Booth decoders 9a to 9d, and the decoding by the second degree Booth algorithm as shown in FIG. 2, is performed.
To the respective Booth decoders 9a to 9p, 3-bit multiplier data or the even bit corresponding to the multiplier input 1 and its higher and lower odd bits are inputted as shifting 2 bits in such a manner that, "0", Y&lt;0&gt; and Y&lt;i&gt; are inputted in the Booth decoder 9a, Y&lt;1&gt;, Y&lt;2&gt; and Y&lt;3&gt; to the Booth decoder 9b, Y&lt;3&gt;, Y&lt;4&gt;and Y&lt;5&gt; to the Booth decoder 9c and so on. And hence, the multipliers having odd order are inputted to the two adjacent Booth decoders. For example, the multiplier bit Y&lt;7&gt;is inputted to both the 4th Booth decoder 9d and the 5th Booth decoder 9e, and the multiplier bit SY&lt;15&gt; is inputted to both the 8th Booth decoder 9h and the 9th Booth decoder 9i.
A signal line through which the odd bit of the multiplier is inputted to the higher Booth decoder is defined as a carry multiplier signal line.
Outputs from the Booth decoders 9a to 9p are respectively inputted to the 1st multiple generating circuit 11a to 16th multiple generating circuit 11p, and in response to these inputs and the rules shown in FIG. 2, the respective multiple generating circuits 11a to 11p generate and output multiples of the multiplicand X corresponding to the values of Y&lt;1:0&gt;, Y&lt;3:2&gt;, Y&lt;5:4&gt;, Y&lt;7:6&gt;, SY&lt;9:8&gt; . . . SY&lt;31:30&gt; and respective carry multiplier signals.
The multiplier outputs from the multiple generating circuits 11a to 11p are that, the multiple output from the multiple generating circuit 11a is outputted intact, as the multiplication result P&lt;1:0&gt; in the multiplication result output 30, and is inputted to the partial product adding circuit 12b, the other multiple outputs from the multiple generating circuit 11b to 11p are respectively inputted to the partial product adding circuits 12b to 12p. Outputs of the partial product adding circuits 12b to 12o are inputted to the partial product adding circuits 12c to 12p, wherein they are added.
The addition results by the partial product adding circuits 12b to 12p are outputted from the multiplication result output 30 as the 64-bit multiplication results P&lt;63:0&gt; to complete the multiplication.
Now, in the above description, though the case of extending the 16-bit signal data and the 8-bit signed data to the 32-bit signed data for multiplication has been described, the case of using 32-bit data is described in the following.
As already described, in the multiplying circuit using the Booth algorithm, though the integers by signed two's complement representation can be executed without pre-processing and post-processing, the unsigned integers can not be operated intact. And hence, in case of using the 32-bit data, it is extended by 1 bit width and is handled as the signed data.
FIG. 8A shows a sign extension necessary for handling 32-bit unsigned integer data as the 33-bit signed number. The sign extension at this time makes an extended bit 32 value "0".
In case of using the 32-bit signed data, as shown in FIG. 8B, a value of the sign bit which is the highest bit 31 is reproduced into the extended bit 32 and is processed as 33-bit singed data.
Since the multiplying circuit for 32 bits is required specially in case of multiplying the 32-bit signed data intact, it is to be understood that it is advantageous from the view point of hardwares to process also the 32-bit signed data after the sign extension to 33 bits in case of using the 32-bit unsigned integer data.
In such multiplication of 33 bits.times.33 bits, as shown in FIG. 9, 17 partial products are produced from the 1st to 17th partial products.
Now, in an array type multiplying circuit of 33 bits.times.33 bits for executing such multiplication in one processing, as apparent from FIG. 5, in general, 17 multiple generating circuits and 16 adding circuits are necessary. Thus when realizing the multiplying circuit on an IC chip as the hardware, a large area is occupied.
And hence, in the case where restriction on the occupied area on the IC chip is severe, the hardwares in which the multiplication is executed after time sharing it into a plural number of operation cycles are used.
The conventional multiplying circuit using such hardwares is described.
FIG. 10 is a block diagram showing an example of realizing such conventional multiplying circuit, and FIG. 11 is a detailed block diagram of a multiplication array circuit 10 which is a portion of the multiplying circuit shown in FIG. 10.
In the conventional example shown in FIG. 10, the hardwares which perform the 33 bits.times.33 bits multiplication in four times are shown. When the operation is executed by such hardwares in four times, the circuit scales of the multiple generating circuits and the adding circuits can be suppressed to about a quarter.
In FIG. 10 and FIG. 11, numeral 1 designates an inputs of a multiplier Y, numeral 2 designates an input of a multiplicand X, numeral 33 designates an initializing control input, numeral 34 designates an operation cycle control input, numeral 5 designates a multiplier dividing circuit, numeral 6 designates a multiplier carry latch, numerals 9a to 9d designate Booth decoders (BD), numeral 10 designates the multiplication array circuit, numerals 11a to 11d designate 1st to 4th multiple generating circuits, and numerals 12a to 12d designate partial product adding circuits (ADD).
In FIG. 11, numerals 13a to 13d designate 1st to 4th carry save type adders (CSA) constituting the partial product adding circuits 12a to 12d, numerals 14a to 14d designate 1st to 4th carry propagation type adders (CPA) constituting the partial product adders 12a to 12d, numeral 15 designates a higher CPA circuit, numeral 16 designates a highest multiple generating circuit, numeral 17 designates a highest partial product adding circuit, numeral 40 designates an intermediate result shift circuit, numeral 41 designates a carry shift circuit included in the intermediate result shift circuit 40, numeral 42 designates a sum shift circuit included in the intermediate result shift circuit 40, numeral 43 designates a CPA carry latch included in the intermediate result shift circuit 40, numeral 30 designates a lower output of the multiplication result Y and numeral 31 designates an higher output of the multiplication result Y.
In the circuit configuration shown in FIG. 10 and FIG. 11, different from the configuration shown in FIG. 5, effective data Y&lt;31:0&gt; in the multiplier input 1 is inputted to the multiplier dividing circuit 5 and divided into four portion by 8 bits, specifically, divided into Y&lt;7:0&gt;, Y&lt;15:8&gt;, Y&lt;23:16&gt; and Y&lt;31:24&gt;, which are respectively outputted successively from the multiplier dividing circuit 5 in time division.
To the Booth decoder 9a, an out, put of the multiplier carry latch 6, 1st and 2nd bit signals from the lower side output of the multiplier dividing circuit 5 are inputted, to the Booth divider 9b, 2nd, 3rd and 4th bit signals from the lower side output of the multiplier dividing circuit 5 are inputted, to the Booth decoder 9c, 4th, 5th and 6th bit signals from the lower side output of the multiplier dividing circuit 5 are inputted, and to the Booth decoder 9d, 6th, 7th and 8th bit signals from the lower side output of the multiplier dividing circuit 5 are inputted.
Outputs of the Booth decoders 9a to 9d are inputted to the multiple generating circuits 11a to 11d respectively. To the 1st partial product adding circuit 12a, outputs of the intermediate result shift circuit 40 and the multiple generating circuit 11a are inputted, to the partial product adding circuit 12b, outputs of the partial product adding circuit 12a and the multiple generating circuit 11b are inputted, to the partial product adding circuit 12c, outputs of the partial product adding circuit 12b and the multiple generating circuit 11c are inputted, and to the partial product adding circuit 12d, outputs of the partial product adding circuit 12c and the multiple generating circuit 11d are inputted.
The highest bit Y&lt;32&gt; of the multiplier input 1 is inputted directly to the highest multiple generating circuit 16, whose output is inputted to the highest partial product adding circuit 17 together with the output of the partial product adding circuit 12d.
An output of the highest partial product adding circuit 17 is inputted to the higher CPA circuit 15, whose output is the multiplication result higher output 31.
Next, the operation of the hardwares shown in FIG. 10 and FIG. 11 is described.
A multiplier Y&lt;31:0&gt; is inputted to the multiplier dividing circuit 5 from the multiplier input 1 in synchronism with the initializing control input 33. At first, the output Y&lt;7:0&gt;, which is the lower 8 bits of the multiplier Y, of the multiplier dividing circuit 5 as the 1st time output.
Simultaneously, the initializing control signal 33 resets the multiplier carry latch 6 and the intermediate result shift circuit 40.
By resetting the multiplier carry latch 6 and the intermediate result, shift circuit 40, "0" is outputted therefrom.
(1) Operation of 1st operation cycle
The first operation is started in synchronism with a rising transition of the operation cycle control input 34.
In the Y&lt;7:0&gt; outputted from the multiplier dividing circuit 5 and "0" outputted from the multiplier carry latch 6, the output of the multiplier carry latch 6 and Y&lt;1:0&gt; are inputted to the Booth decoder 9a, Y&lt;3:1&gt; is inputted to the Booth decoder 9b, Y&lt;5:3&gt; is inputted to the Booth decoder 9c and Y&lt;7:6&gt; is inputted to the Booth decoder 9d, and decoded by Booth algorithm.
The 1st, 2nd, 3rd and 4th multiplier generating circuits 11a to 11d respectively generate and output multiples of the multiplicand X corresponding to values of Y&lt;1:0&gt;, Y&lt;3:2&gt;, Y&lt;5:4&gt; and Y&lt;7:6&gt;, in response to the outputs from the respective Booth decoders 9a to 9b and the rules shown in FIG. 2.
The multiple outputs outputted from the multiple generating circuits 11a to 11d are inputted to and added in the carry save type adding circuits (CSA) 13a to 13d in the 1st to 4th adders 12a to 12d.
In the 1st CSA 13a, the output of the 1st multiple generating circuit 11a and an initial value "0" of the intermediate result shift circuit 40 are added, and the addition result is outputted in a set of carry (C) and sum (S). A portion of which corresponding to the lower 2 bits is inputted to the 1st CPA 14A, and a remaining portion is inputted to the 2nd CSA 11b close to the lower bit side.
Thereafter, in the same manner, from the 2nd CSA 13b to 4th CSA 13d, the multiplier outputs are added successively as shifting the digits by 2 bits. As the result of addition, the operation corresponding to Y&lt;7:0&gt;.times.X is executed.
Portions corresponding to the lower 2 bits of the outputs from the 1st CSA 13a to 4th CSA 14d in the operation result are inputted to the 1st CPA 14a to 4th CPA 14d, thereby the operation including a carry propagation is executed and the 8-bit addition result P&lt;7:0&gt; is outputted from the multiplication result lower output 30.
While, the higher portions of the operation result are outputted from the 4th CSA 13d in the form of a set of carry and sum, and inputted directly to the intermediate result shift circuit 40, wherein the carry output is latched by the carry shift circuit 41 and the sum output is latched by the sum shift circuit 42.
The carry output, of the 4th CPA 14d is saved in the CPA carry latch 43 in the intermediate result shift circuit 40, and the Y&lt;7&gt; value is saved in the multiplier carry latch 6.
Hereupon, the operation of saving the Y&lt;7&gt; value in the multiplier carry latch 6 is described.
As aforementioned, the 1st operation cycle starts in synchronism with the rising transition of the operation cycle control input 34, and the multiplier carry latch 6 outputs "0" latched at the time of initialization to give it to the Booth decoder 9a.
Now, the operation cycle control input 34 is connected to the multiplier carry latch 6 at its terminal T, and the highest output bit from the multiplier dividing circuit 5 is connected at its terminal D. Thus, the multiplier carry latch 6 outputs "0" in synchronism with the rising transition of the operation cycle control input 34, and latches Y&lt;7&gt; outputted from the multiplier dividing circuit 5.
The 1st operation cycle has been operated as described above.
In the 1st operation cycle, the highest multiplier generating circuit 16 to which the highest multiplier bit Y&lt;32&gt; is inputted and the highest partial product adding circuit 17 do not perform meaningful operations.
(2) Operation of 2nd operation cycle
Successively, the 2nd operation cycle is started in synchronism with changes in the operation cycle control signal 4.
In the 2nd operation cycle, Y&lt;15:8&gt; is outputted from the multiplier dividing circuit 5 as the 2nd output, Y&lt;7&gt; which was latched in the 1st operation cycle is outputted from the multiplier carry latch 6, and the higher operation result of the 1st operation cycle is outputted from the intermediate result shift circuit 40 in the form of a set of carry and sum.
Simultaneously, the multiplier carry latch 6 latches Y&lt;15&gt; outputted from the multiplier dividing circuit 5.
Also in the 2nd operation cycle, the multiplier is decoded and the multiples are generated in the same manner as in the 1st operation cycle, and the multiples are outputted from the multiple adding circuits 12a to 12d. The multiples generated in the 2nd operation cycle are the portions corresponding to Y&lt;15:8&gt;.
To the adding circuits 12a to 12d, in addition to the multiples obtained in the 2nd operation cycle, the higher result of the 1st operation cycle is also inputted from the intermediate result shift circuit 40 for addition. As the result of addition, a value excluding the lower 8 bits of Y&lt;15:0&gt;.times.X is obtained close to the lower bit side.
The lower 8 bits of the addition result are outputted to the multiplication result lower output 30 from the 1st CPA 14a to 4th CPA 14d as P&lt;15:8&gt;, and the higher bits are again inputted to the intermediate result shift, circuit 40 to complete the 2nd operation cycle.
Thereafter, the 3rd and 4th operation cycles are executed in the same manner, and P&lt;23:16&gt; and P&lt;31:24&gt; are outputted in order from the multiplication result lower output 30.
In the 4th operation cycle which is the final operation cycle, the higher bits outputted from the 4th CSA 13d are the value excluding lower 32 bits of Y&lt;31:0&gt;.times.X. For obtaining the multiplication result of 33 bits, the highest multiple corresponding to Y&lt;32&gt; must be added. For this purpose, the highest multiple generating circuit 16 and the highest partial product adding circuit 17 are provided.
Output of the 4th CSA 13d is inputted to the highest partial product adding circuit 17, wherein it is added to output of the highest multiple generating circuit 16 corresponding to Y&lt;32 &gt;.
Since the operation result hitherto is obtained in the form of a set of carry and sum, the addition including the carry propagation is further executed in the higher CPA circuit 15, and the addition result is outputted to the multiplication result higher output 31.
FIG. 12 to FIG. 14 are views for particularly describing the carry shift circuit 41 which is a portion of the multiplication array shown in FIG. 11. FIG. 12 is a block diagram showing an example of configuration of the carry shift circuit 41, FIG. 13 is a truth table for explaining its operation and FIG. 14 is a circuit diagram showing an example of circuit configuration in case of realizing the carry shift circuit 41 by a MOS transistor circuit.
In FIG. 12, numeral 60 designates a D flip-flop with reset constituting the carry shift circuit 41, numeral 51 designates an inverter, numeral 52 designates a transmission gate, numeral 53 designates a MOS transistor and numeral 54 designates a NOR gate.
The carry shift circuit 41 is that, the initializing control input 33 is inputted to a reset terminal R, the carry intermediate result 24 is inputted to a data terminal D, the operation cycle control input 34 is inputted to a trigger terminal T, and a shift circuit output is outputted from an output terminal Q. Thus, the carry shift circuit 41 is reset by the initializing control input 33 and propagates the carry intermediate result 24 to the output in synchronism with the rising transition of the operation cycle control input 34.
These operation are summarized in the truth table shown in FIG. 13.
The D flip-flop with reset 60 which is an essential portion of the carry shift circuit 41 can be constituted as shown in FIG. 14, for example, by using a CMOS.
The sum shift, circuit 42 can also be constituted in the same way as the carry shift circuit 41.
How the multiplication shown in a schematic view of FIG. 9 is divided in the multiplying circuit shown in FIG. 10 is shown in schematic views of FIG. 15 and FIG. 16.
The 0th to 3rd partial products are added in the 1st operation cycle, the 4th to 7th partial products are added in the 2nd operation cycle, the 8th to 11th partial products are added in the 3rd operation cycle, and in the 4th operation cycle, in addition to the 12th to 15th partial products, the 16th partial product which is the highest partial product is added.
At this time, a higher value of the operation result of the previous cycle is added to the operation of the following cycle as the intermediate result. And, in the final 4th operation cycle, all of the partial products are added and the multiplication result is obtained.
Since the conventional multiplying circuit is constituted as described above, gates for realizing an OR function and an AND function for every bits are required in the sign extension circuit, thus, for example, in case of constituting such a multiplying circuit on a chip as a portion of a computer, a very large occupied area of the chip is required due to transistors for realizing the gates, results in a problem of chip utilization efficiency.
In the configuration producing the remainder in division of the multiplier bits as in case of dividing the 33 bits.times.33 bits multiplication into 4 operation cycles shown as the conventional example, an extra multiple generating circuit and adding circuit are required for adding the partial product of the remained bits.
It is believed that, numerals used in a digital processor or in a microprocessor and the like are usually in a bit width of two's power number such as 8, 16 and 32 bits, so that the division can be performed without remainders. However, in case of using unsigned binary numbers in the multiplying circuit utilizing the Booth algorithm, since the bit width of the multiplier inputted to the multiplying circuit must be extended by 1 bit from the original bit width, it is necessary to add a circuit for adding the partial product for the 1 bit extension portion, enlarging the circuit scale.